<!doctype html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport"
          content="width=device-width, user-scalable=no, initial-scale=1.0, maximum-scale=1.0, minimum-scale=1.0">
    <meta http-equiv="X-UA-Compatible" content="ie=edge">
    <title>最强连一连地图生成器</title>
</head>
<body>

</body>
<script>
    var map1 = {
        t: "4x3",
        a: [
            2, 1, 1, 1,
            1, 0, 0, 1,
            1, 1, 1, 1
        ],
        l: [0, 1, 2, 3, 7]
    };
    var map2 = {
        t: "4x3",
        a: [
            1, 1, 1, 1,
            1, 0, 2, 1,
            1, 1, 1, 1
        ]
    };
    var map3 = {
        t: "4x3",
        a: [
            0, 0, 1, 1,
            1, 2, 1, 1,
            1, 1, 1, 1
        ],
    };

    var map4 = {
        t: "6x6",
        a: [
            0, 0, 1, 1, 1, 1,
            2, 1, 1, 1, 1, 1,
            1, 1, 1, 1, 1, 1,
            1, 1, 1, 1, 1, 1,
            1, 1, 1, 1, 1, 1,
            1, 1, 1, 1, 1, 1
        ]
    }


    function MP() {
        /**
         * 是否在地图内
         * @param p
         * @returns {boolean}
         */
        this.in_map = function (p) {
            if (p >= 0 && p < this.col * this.row) {
                return true;
            }
            return false;
        };

        /**
         * 是否可以通行
         *  @param p
         * @returns {boolean}
         */
        this.is_allow = function (p) {
            return this.map[p] >= 1;
        };
        /**
         * 上一个节点
         * @param p
         * @returns {*}
         */
        this.upPoint = function (p) {
            var np = p - this.col;
            return this.in_map(np) ? np : false;
        };
        /**
         * 下一个节点
         * @param p
         * @returns {boolean}
         */
        this.downPoint = function (p) {
            var np = p + this.col;
            return this.in_map(np) ? np : false;
        };
        /**
         * 左一个节点
         * @param p
         * @returns {*}
         */
        this.leftPoint = function (p) {
            var np = p - 1;
            var row = parseInt(p / this.col);
            var nrow = parseInt(np / this.col);
            return (row === nrow) ? (this.in_map(np) ? np : false) : false;
        };
        /**
         * 右一个节点
         * @param p
         * @returns {boolean}
         */
        this.rightPoint = function (p) {
            var np = p + 1;
            var row = parseInt(p / this.col);
            var nrow = parseInt(np / this.col);
            return (row === nrow) ? (this.in_map(np) ? np : false) : false;
        };
    }

    /**
     * 解析地图
     */
    function Game(map) {
        MP.call(this);
        var temp = map.t.split('x');
        this.col = parseInt(temp[0]);
        this.row = parseInt(temp[1]);
        this.map = map.a;
        this.path = [];
        this.flag = false;
        var allowLength = 0;
        for (var i = 0; i < this.map.length; i++) {
            if (this.map[i] > 0) {
                allowLength += 1;
            }
        }
        this.allowLength = allowLength;
        this.dePath = function () {
            //找到地地图的起始位置
            var startPoint = this.map.indexOf(2);
            this.findNext(startPoint);
            return this.path.length === this.allowLength ? this.path : false;
        };
        /**
         * 寻找下一个点
         */
        this.findNext = function (p) {
            var next;
            this.path.push(p);
            if (this.allowLength === this.path.length) {
                //path 已走完全部
                this.flag = true;
                return true;
            }
            var that = this;
            ['up', 'down', 'left', 'right'].forEach((vo) => {
                switch (vo) {
                    case 'up':
                        next = that.upPoint(p);
                        break;
                    case 'down':
                        next = that.downPoint(p)
                        break;
                    case 'left':
                        next = that.leftPoint(p);
                        break;
                    case 'right':
                        next = that.rightPoint(p);
                }
                if (next !== false && this.is_allow(next) && this.path.indexOf(next) === -1) {
                    //如果不在栈内
                    this.findNext(next);
                    if (this.flag) {
                        return true;
                    }
                    this.path.pop();
                }
            });
        }


    }

    /**
     * 生成地图方法一
     * @param t  4x3
     * @constructor
     */
    function CreateMap() {

        this.closeProbability = 30; //生成 阻路节点的概率
        this.create = function (t,closeProbability) {
            if(closeProbability){
                this.closeProbability = closeProbability;
            }
            var temp = t.split('x');
            this.col = parseInt(temp[0]);
            this.row = parseInt(temp[1]);
            var map;
            var i = 0;
            do {
                map = {
                    a:this.structMap(),
                    t:t
                };
                map = this.checkMap(map);
                i++;
            } while ( map === false && i < 10000); //防止死循环
            return map;
        };

        /**
         * 构建地图
         */
        this.structMap = function () {
            var a = [];
            for (var i = 0; i < this.col * this.row; i++) {
                var r = random(0, 100);
                a[i] = (r > this.closeProbability) ? 1 : 0;
            }
            a = this.startPoint(a);
            return a;
        };
        /**
         * 检查地图能否走完
         * @param map
         * @returns {boolean}
         */
        this.checkMap = function (map) {
            var game = new Game(map);
            var l = game.dePath();
            if (l === false) {
                return false;
            }
            map.l = l;
            return map;
        };

        this.startPoint = function (a) {
            do {
                var r = random(0, this.col * this.row - 1);
            } while (a[r] === 0);
            a[r] = 2; //设置起始位置
            return a;
        };
    }

    /**
     * 生成地图方法二
     * 优化CreateMap， 先生成线，再生成地图
     * @constructor
     */
    function CreateLine() {
        this.path = [];
        this.flag= false;
        MP.call(this);
        this.clear = function(){
          this.path = [];
          this.map  = [];
          this.flag= false;
        };
        /**
         *
         * @param t 地图大小
         * @param pathLength  连线要经过的点数量
         * @returns {{t: *, a: *, l: *}}
         */
        this.create = function (t,pathLength) {
            var temp = t.split('x');
            this.col = parseInt(temp[0]);
            this.row = parseInt(temp[1]);
            if(pathLength){
                this.pathLength = pathLength;
            }else{
                var r =  (this.col * this.row) - random(this.col,this.col+this.row);
                var p = r / (this.col * this.row);
                if(p < 0.5){
                    r += random(2,3);
                }
                else if(p < 0.7){
                    r += random(1,2);
                }else if(p > 0.85){
                    r -= random(2,3);
                }
                this.pathLength = r;
            }
            this.initMap();
            var startPoint = random(0, this.col * this.row - 1);
            this.map[startPoint] = 2;
            this.findNext(startPoint);
            this.renderMap();
            return {
                t:t,
                a:this.map,
                l:this.path
            };
        };

        //初始化地图
        this.initMap = function () {
            var a = [];
            for (var i = 0; i < this.col * this.row; i++) {
                a[i] =  0;
            }
             this.map = a;
        };

        this.renderMap = function(){
          for(var i = 0; i< this.map.length ; i++){
              var p = this.map[i];
              if(this.path.indexOf(i) !== -1 && p !== 2){
                  this.map[i] = 1;
              }
          }
        };




        this.findNext = function (p) {
            var next;
            this.path.push(p);
            if (this.pathLength === this.path.length) {
                //path 已走完全部
                // console.log('66完了')
                // console.log(this.path)
                this.flag = true;
                return true;
            }

            var that = this;
            var direction = [
                ['up', 'down', 'left', 'right'],
                ['up', 'down', 'right', 'left'],
                ['up', 'left', 'down', 'right'],
                ['up', 'left', 'right', 'down'],
                ['up', 'right', 'down', 'left'],
                ['up', 'right', 'left', 'down'],

                ['down', 'left', 'up', 'right'],
                ['down', 'left', 'right', 'up'],
                ['down', 'right', 'left', 'down'],
                ['down', 'right', 'down', 'left'],
                ['down', 'up', 'left', 'right'],
                ['down', 'up', 'right', 'left'],


                ['left', 'down', 'up', 'right'],
                ['left', 'down', 'right', 'up'],
                ['left', 'right', 'up', 'down'],
                ['left', 'right', 'down', 'up'],
                ['left', 'up', 'down', 'right'],
                ['left', 'up', 'right', 'down'],

                ['right', 'down', 'left', 'up'],
                ['right', 'down', 'up', 'left'],
                ['right', 'left', 'down', 'up'],
                ['right', 'left', 'up', 'down'],
                ['right', 'up', 'left', 'down'],
                ['right', 'up', 'down', 'left'],
            ];
            var key = random(0, 23);//随机出一个方向
            direction[key].forEach((vo) => {
                if (this.flag) {
                    return true;
                }
                switch (vo) {
                    case 'up':
                        next = that.upPoint(p);
                        break;
                    case 'down':
                        next = that.downPoint(p)
                        break;
                    case 'left':
                        next = that.leftPoint(p);
                        break;
                    case 'right':
                        next = that.rightPoint(p);
                }
                if (next !== false  && this.path.indexOf(next) === -1) {
                    //如果不在栈内
                    this.findNext(next);
                    if (this.flag) {
                        return true;
                    }
                    this.path.pop();
                }
            });

        }
    }

    function random(lower, upper) {
        return Math.floor(Math.random() * (upper - lower)) + lower;
    }
    // var game1 = new Game(map1);
    // var game2 = new Game(map2)
    // var game3 = new Game(map3);
    // var game4 = new Game(map4);
    // console.log(game1.dePath());
    // console.log(game2.dePath());
    // console.log(game3.dePath());
    // console.log(game4.dePath());


    // var c = new CreateMap;
    // var m = {};
    // var i = 0;
    // while(i< 196){
    //     if(i< 30){
    //         var map = c.create('4x3',random(30,40));
    //     } else if(i < 50){
    //         var map = c.create('4x4',random(35,45));
    //     } else if(i<70){
    //         var map = c.create('5x4',random(35,45));
    //     } else if(i<100){
    //         var map = c.create('5x5',random(40,45));
    //     } else if(i<150){
    //         var map = c.create('6x5',random(40,45));
    //     } else {
    //         var map = c.create('6x6',random(40,45));
    //     }
    //     // console.log(map)
    //     if(!m.hasOwnProperty(map.a.toString())){
    //         m[map.a.toString()] = map;
    //         i++;
    //     }
    // }
    // var maps = [];
    // var k = 0;
    // for(var i in m){
    //     maps[k] = m[i];
    //     k++;
    // }
    // maps = JSON.stringify(maps)
    // console.log(maps)



    var lineMap = new CreateLine();
    var m = {};
    var i = 0;
    // while (i< 100){
    //     if(i<50){
    //         var map = lineMap.create('5x5');
    //     }else{
    //         var map =  lineMap.create('6x5')
    //     }
    //     lineMap.clear();
    //     //     // console.log(map)
    //         if(!m.hasOwnProperty(map.a.toString())){
    //             m[map.a.toString()] = map;
    //             i++;
    //         }
    // }
    while(i< 450){
            var map =  lineMap.create('6x6');
        // } else if(i<= 150){
        //     var map = lineMap.create('6x5');
        // } else if(i <= 200) {
        //     var map = lineMap.create('6x6');
        // }
        lineMap.clear();
        // console.log(map)
        if(!m.hasOwnProperty(map.a.toString())){
            m[map.a.toString()] = map;
            i++;
        }
    }
    var maps = [];
    var k = 0;
    for(var i in m){
        maps[k] = m[i];
        k++;
    }
    maps = JSON.stringify(maps)
    console.log(maps)
</script>
</html>